/*
 * BinarySearchTree.h
 * The implementation of a typical binary search tree.
 *  Created on: 2013-1-7
 *      Author: EthanHuang
 */

#ifndef BINARYSEARCHTREE_H_
#define BINARYSEARCHTREE_H_
#include <iostream>

template<typename ComparableType> class BinarySearchTree
{
public:
	BinarySearchTree();
	BinarySearchTree(const BinarySearchTree& rhs);
	~BinarySearchTree();

	const ComparableType& findMax() const;
	const ComparableType& findMin() const;
	bool contains(const ComparableType& x) const;
	bool isEmpty() const;
	void printTree() const;

	//Delete all BinaryNode that in the BinarySearchTree
	void makeEmpty();
	void insert(const ComparableType& x);
	void remove(const ComparableType& x);
	//make a clone of a BinarySearchTree
	const BinarySearchTree& operator=(const BinarySearchTree& tree);

private:

	//
	struct BinaryNode
	{
		BinaryNode(const ComparableType& elm, BinaryNode* lt, BinaryNode* rt) :
				elm(elm), left(lt), right(rt)
		{
		}
		~BinaryNode()
		{
			left = right = NULL;
		}
		//The actual BinaryNode should hold a element that inherit Comparable
		//interface
		ComparableType elm;
		BinaryNode *left;
		BinaryNode *right;
	};

	//Note: the reference to the pointer of a tree node, makes it easy to
	//modify the tree
	BinaryNode* _root;
	void _insert(const ComparableType& x, BinaryNode* & tree) const
	{
		if(NULL == tree)
		{
			tree = new BinaryNode(x, NULL, NULL);
		}
		else if( x < tree->elm)
		{
			_insert(x, tree->left);
		}
		else
		{
			_insert(x, tree->right);
		}
		else
		{}
			//Duplication, nothing to do here
	}

	void _remove(const ComparableType& x, BinaryNode* & tree) const
	{
		if(NULL == tree)
		{
			return;
		}
		if(x < tree->elm)
		{
			_remove(x, tree->left);
		}
		else if (x > tree->elm)
		{
			_remove(x, tree->right);
		}
		//Find the element to be removed
		else if (tree->left != NULL && tree->right != NULL) //With two children
		{
			//swap the minimal element in the right subtree and recursive remove
			tree->elm = _findMin(tree->right)->elm;
			_remove(x->elm, tree->right);
		}
		else //With one child
		{
			BinaryNode* old = tree;
			tree = (tree->left != NULL) ? tree->left : tree->right;
			delete tree;
		}
	}

	BinaryNode* _findMax(BinaryNode* t) const
	{
		if(NULL != t)
		{
			while(NULL != t->right)
				t= t->right;
			return t;
		}
		return NULL;
	}

	BinaryNode* _findMin(BinaryNode* x) const
	{
		if(NULL == x)
		{
			return NULL;
		}
		if(NULL == x->left)
		{
			return x;
		}
		return _findMin(x->left);
	}

	bool _contains(const ComparableType& x, BinaryNode* t) const
	{
		if(NULL == t)
		{
			return false;
		}
		else if(x > t->elm)
		{
			_contains(x, t->right);
		}
		else if(x < t->elm)
		{
			_contains(x, t->left);
		}
		else
			return true;
	}

	void _makeEmpty(BinaryNode* node)
	{
		if( NULL != node)
		{
			_makeEmpty(node->left);
			_makeEmpty(node->right);
			delete node;
		}
		node = NULL;
	}

	void _printTree(BinaryNode* node) const
	{
		if(NULL != node)
		{
			std::cout<<node->elm<<" ";
			_printTree(node->left);
			_printTree(node->right);
		}
	}

	BinaryNode* clone(BinaryNode* node) const
	{
		if(NULL == node)
			return NULL;
		return new BinaryNode(node->elm, clone(node->left), clone(node->right) );
	}

};

template<typename ComparableType>
inline BinarySearchTree<ComparableType>::BinarySearchTree() :
		_root(NULL)
{
}

template<typename ComparableType>
inline BinarySearchTree<ComparableType>::BinarySearchTree(
		const BinarySearchTree& rhs)
{
	_root = clone(rhs._root);
}

template<typename ComparableType>
inline BinarySearchTree<ComparableType>::~BinarySearchTree()
{
	makeEmpty();
}

template<typename ComparableType>
inline const ComparableType& BinarySearchTree<ComparableType>::findMax() const
{
	return _findMax(_root)->elm;
}

template<typename ComparableType>
inline const ComparableType& BinarySearchTree<ComparableType>::findMin() const
{
	return _findMin(_root)->elm;
}

template<typename ComparableType>
inline bool BinarySearchTree<ComparableType>::contains(
		const ComparableType& x) const
{
	return _contains(x, _root);
}

template<typename ComparableType>
inline bool BinarySearchTree<ComparableType>::isEmpty() const
{
	return this->_root = NULL ? true : false;
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::printTree() const
{
	std::cout<<"The tree is :"<<std::endl;
	_printTree(_root);
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::makeEmpty()
{
	_makeEmpty(_root);
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::insert(const ComparableType& x)
{
	_insert(x, _root);
}

template<typename ComparableType>
inline void BinarySearchTree<ComparableType>::remove(const ComparableType& x)
{
	_remove(x, _root);
}

template<typename ComparableType>
inline const BinarySearchTree& BinarySearchTree<ComparableType>::operator =(
		const BinarySearchTree& tree)
{
	if(tree != this)
	{
		makeEmpty();
		_root = clone(tree._root);
	}
	return *this;
}

#endif /* BINARYSEARCHTREE_H_ */
